﻿public class Solution34
{
    public int[] SearchRange(int[] nums, int target)
    {
        int[] res = new int[2];
        int len = nums.Length;

        int low = SearchLower(nums, target);
        int high = SearchHigher(nums, target);
        Console.WriteLine(low);
        Console.WriteLine(high);

        if (low <= high && high < len && nums[low] == target && nums[high] == target)
        {
            res[0] = low;
            res[1] = high;
        }
        else
        {
            res[0] = -1;
            res[1] = -1;
        }
        return res;
    }

    private int SearchLower(int[] nums, int target)
    {
        int len = nums.Length;
        int left = 0;
        int right = len - 1;
        int res = 0;

        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (target <= nums[mid])
            {
                right = mid - 1;
                res = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return res;
    }

    private int SearchHigher(int[] nums, int target)
    {
        int len = nums.Length;
        int left = 0;
        int right = len - 1;
        int res = 0;

        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (target < nums[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
                res = mid;
            }
        }

        return res;
    }

    private class Program34
    {
        private static void Main34(string[] args)
        {
            // int[] nums = [5, 7, 7, 8, 8, 10];
            int[] nums = [];
            int target = 0;
            Solution34 solution = new Solution34();
            int[] res = solution.SearchRange(nums, target);
            Console.WriteLine(res[0] + "," + res[1]);
        }
    }
}